//1035.不相交的线
//https://leetcode.cn/problems/uncrossed-lines
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(),n = nums2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        //dp[i][k]表示nums1前i个数字和nums2前k个数字中有多少条直线
        for(int i = 1;i<=m;++i)
            for(int k = 1;k<=n;++k)
            {
                //如果当前下标的数可以组成直线 则在上一次结果的基础上+1
                if(nums1[i-1]==nums2[k-1]) dp[i][k] = dp[i-1][k-1]+1;
                //否则就不选nums1或nums2中的一个数 选择两者的最大值
                else dp[i][k]=max(dp[i][k-1],dp[i-1][k]);
            }

        return dp[m][n];
    }
};